# The original paper about dot diffustion is
# dl.acm.org/doi/10.1145/35039.35040
import numpy as np
from numpy._typing import NDArray

diffmat: NDArray = np.array([
	[0,  8, 2, 10],
	[12, 4, 14, 6],
	[3, 11, 1,  9],
	[15, 7, 13, 5]
])

def dot_diffusion(img: NDArray):
	"""
	:param img: the greyscale image array
	:return: halftone image through dot diffusion
	"""
	h, w = np.array(img).shape
	dh, dw = diffmat.shape
	
	# prepare the generated img
	out_img: list = [[0] * w for _ in range(h)]
	
	# split image to every block
	for i in range(0, h, dh):
		for j in range(0, w, dw):
			block = img[i:i+dh, j:j+dw]  # get block
			
			# apply error diffusion to blocks
			for di in range(dh):
				for dj in range(dw):
					if i + di < h and j + dj < w: # boundary detect
						threshold = diffmat[di, dj]
						if block[di, dj]/255 > threshold/16:
							out_img[i+di][j+dj] = 255
						else:
							out_img[i+di][j+dj] = 0
						
					err = block[di, dj].astype(np.int16) - out_img[i+di][j+dj]
					# simple diffusion, only two directions
					if dj + 1 < dw and j + dj + 1 < w:
						img[i+di, j+dj+1] += err * 0.5
					if di + 1 < dh and i + di + 1 < h:
						img[i+di+1, j+dj] += err * 0.5
	
	return out_img
